#include "CostumUtils.h"
#include <vector>

using std::vector;

/*
@parameters:
--the array ready to sorted.
@return:

------->time complexity: O(n^2)
first find the smallest item in the array, then exchange it with the first item in the array,
then find the next smallest item and exchang it with the second item, continue in this way
until array is sorted.
*/
void selectionSorted(vector<int> & list)
{
	auto length = list.size();
	for (size_t i = 0; i < length; i++) {
		int temp = 0;
		int min = i;
		for (size_t j = i + 1; j < length; j++) {
			if (list[j] <= list[min]) min = j;
		}
		temp = list[min];
		list[min] = list[i];
		list[i] = temp;
	}
}

/*
@parameters:
  --the array ready to sorted.
@return:
  --the array already sorted.

------->time complexity: O(n^2)

pre:the a, b, c already sorted.
list: a, b, c, d, e, f, g, d
			^  ^
			|  |
			|   `----------the key, index is i, use to compare with the front number.
			 `------------the index is j.
if the key(number d) is less than the c, let d = c, then compare key and b until index = 0,
*/
void insertionSorted(vector<int> & list)
{
	auto length = list.size();
	for (size_t i = 1; i < length; i++) {
		int key = list[i];
		int j = i - 1;
		//if use key > list[j] it's descending order,
		//if use key < list[j] it's ascending order.
		while (j >= 0 && key < list[j]) {
			list[j + 1] = list[j];
			j--;
		}
		list[j + 1] = key;
	}
}

/*
@parameters:
--the array ready to sorted.
@return:

------->time complexity: O(n^(3/2))

pre:the a, b, c already sorted.we choose 2 to make increment(list length / 2)
so the increment is 4 in first time cutting.
list: a, b, c, d, e, f, g, h
so the array is divided into the four sub array[a, e],[b, f],[c, g],[d, h]

first, we choose a increment, and use it to cut the array to some sub array,
then we use insertion sort those sub array, then make increment = increment / 2,
continue do cutting and sorted until increment = 0.
*/
void refinedShellSorted(vector<int> & list)
{
	auto length = list.size();
	int increment = length / 2;
	while (increment != 0)
	{
		for (int i = 0; i < increment; i++) {
			int times = 0;
			while ((i + times * increment) < length) times++;
			//insertion sorts
			for (size_t j = i + increment; times > 1; j += increment, times--) {
				int key = list[j];
				int k = j - increment;
				//Warining, if the type of i is a unsigned into, and k is into, so compare i and k 
				//will cause unexpected state.so we should make i be a into.
				while (k >= i && key < list[k]) {
					list[k + increment] = list[k];
					k -= increment;
				}
				list[k + increment] = key;
			}
		}
		increment /= 2;
	}
}